//给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 
//
// 
//
// 示例 1: 
//
// 输入: [1,2,0]
//输出: 3
// 
//
// 示例 2: 
//
// 输入: [3,4,-1,1]
//输出: 2
// 
//
// 示例 3: 
//
// 输入: [7,8,9,11,12]
//输出: 1
// 
//
// 
//
// 提示： 
//
// 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。 
// Related Topics 数组 
// 👍 834 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：缺失的第一个正数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P41_FirstMissingPositive {
    public static void main(String[] args) {
        Solution solution = new P41_FirstMissingPositive().new Solution();
        MyUtil.print(solution.firstMissingPositive(MyUtil.createArray(7, 8, 9, 11, 12)));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int firstMissingPositive(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 1;
            }
            int L = 0; // <L的都是有效区
            int R = arr.length; // >R的都是垃圾区
            while (L < R) {
                // L上的位置有效
                if (arr[L] == L + 1) {
                    L++;
                    continue;
                }
                // L上的位置无效，R向左移动一位并与L交换
                if (arr[L] <= L || arr[L] > R || arr[arr[L] - 1] == arr[L]) {
                    swap(arr, L, --R);
                    continue;
                }
                // L与(arr[L]-1)交换
                swap(arr, L, arr[L] - 1);
            }
            return L + 1;
        }

        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}